class Solution(object):
    def checkValidString(self, s):
        """
        :type s: str
        :rtype: bool
        """
        s_c = 0
        l_c = 0
        for i in range(len(s)):
            if s[i] == '(':
                l_c += 1
            if s[i] == ')':
                if l_c > 0:
                    l_c -= 1
                else:
                    if s_c > 0:
                        s_c -= 1
                    else:
                        return False
            if s[i] == '*':
                s_c += 1
        if l_c > s_c:
            return False
        s_c = 0
        r_c = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == ')':
                r_c += 1
            if s[i] == '(':
                if r_c > 0:
                    r_c -= 1
                else:
                    if s_c > 0:
                        s_c -= 1
                    else:
                        return False
            if s[i] == '*':
                s_c += 1
        if r_c > s_c:
            return False
        return True


data = Solution()
s = "(*)"
print(data.checkValidString(s))
